A cryptography is roughly divided into two categories: public key cryptography and a common key cryptography. The public key cryptography uses different keys for encryption and decryption and ensures the security of transmitting information by letting only a receiver know a decryption key for decoding a cipher text (private key) instead of publicly opening a encryption key (public key). However, the common key cryptography uses the same keys for encryption and decryption and ensures the security of transmitting information by preventing the private key from being known by a third party other than a transmitter and a receiver.
When the common key encryption is compared with the public key encryption, the common key encryption has an advantage that its process speed is faster and it can be compactly implemented. Therefore, when an encryption function is added to a small-size device, such as a cellular phone, an IC card and the like, a common key encryption is often used. Since its process speed is higher and it can encrypts/decrypts information in real time, it can be also used for information communications in the fields of broadcast and communications.
The common key encryption is divided into two categories: stream cipher and block cipher. Currently, the block cipher is often used for the common key encryption from the viewpoint of security. The block cipher divides a plaintext (text to be encrypted) into groups with a certain bit length (called a “block”) and encrypts it in units of groups. The bit length of a block being the process unit of encryption is called a “block length”.
As to the common key block cipher, various algorithms are known according to its block length. DES, AES, SC2000, MISTY (MISTY 1 and MISTY 2), KASUMI and the like are its typical ones. These block cipher algorithms are implemented by software or hardware.
FIG. 1 is a general basic configuration of data conversion function processor in a common key encryption.
The data conversion function processor 1 in common key encryption includes an extended key generation unit 10 and a round process unit 20. The extended key generation unit 10 generates a plurality of extended keys K0, K1, K2, . . . and Kn (n is a natural number) from an input private key (common key) and outputs them to the round process unit 20. The round process unit 20 converts and outputs an input plaintext to an cipher text by using the plurality of extended keys K1 through Kn inputted from the extended key generation unit 10.
Next, the MISTY 1 being one of common key encryptions will be explained. The MISTY 1 is a common key encryption with a 64-bit block length and a 128-bit key length, and converts a 64-bit plaintext to a 64-bit cipher text by using a 128-bit private key. Therefore, a data conversion function processor in MISTY 1 is configured in such a way that a 128-bit private key and a 64-bit plaintext are input to extend key generation unit 10 and the round process unit 20, respectively.
[Summary of MISTY 1]
The detailed configuration of the MISTY1 data conversion function processor will be explained below.
{Configuration of Round Process Unit}
Firstly, the configuration of the round process unit 20 will be explained. In the MISTY 1, it is regulated that the number of stages of a round process is the multiple times of 4 and eight stages are recommended. Therefore, the configuration of the round process unit 20 whose number of stages is 8 will be explained below.
FIGS. 2A and 2B are the configurations of the MISTY 1 round process unit. FIGS. 2A and 2B are the configurations of round process units for encryption and decryption, respectively.
As illustrated in FIGS. 2A and 2B, the MISTY1 round process unit is Feistel-structured. Next, the Feistel structure will be briefly explained. The Feistel structure divides an input into two of right and left blocks. Then, it inputs the left block (hereinafter called a “block L”) to an F function (FO function in the case of the MISTY 1), calculates the exclusive OR of the output of the F function and the right block (hereinafter called a “block R”). Then, after the completion of the logical calculation process, it replaces the block L with the block R. The F function is also called a “round function”. The F function is a “data conversion function” in abroad sense.
As illustrated in FIG. 2A, the MISTY 1 round process unit 20a for encryption is composed by combining FL functions 30a (FL1-FL10), FO functions 40 (FO1-FO8) and an exclusive OR 50. As illustrated in FIG. 2B, the round process unit 20b for decryption is composed by vertically inverting and arranging the respective components of the round process unit 20a for encryption and an FL−1 function 30b being its inverse function is arranged instead of the FL function 30a. The MISTY 1 round process unit 20a for encryption inputs a 64-bit plaintext P, converts it to a 64-bit cipher text C and outputs it. The MISTY 1 round process unit 20b for decryption inputs the 64-bit cipher text C, decrypts it to the 64-bit plaintext P and outputs it. The MISTY 1 round process unit 20a for encryption and the MISTY 1 round process unit for decryption 20b perform encryption and decryption processes, respectively, using the extended keys generated by the extended key generation unit 10.
The MISTY 1 generates a 128-bit extended key K′ from the 128-bit private key K by performing an extended key generation process. This extended key K′ is used for the FO function, the FL function, the FL1 function and an FI function. The detailed generation process of an extended key will be described later.
The configurations of a FOi (i=1 to 8) and a FIij (i=1 to 8 and j=1 to 8) are illustrated in FIGS. 3 and 4, respectively. The configurations of a FLi (i=1 to 8) and a FLi−1 (i=1 to 8) are illustrated in FIGS. 5A and 5B, respectively.
As illustrated in FIG. 3, the FO function is a function in a MISTY structure which inputs 32-bit data, converts it to 32-bit data and outputs it and includes an FI function and an exclusive OR. The 32-bit input data is divided into two of 16 bits and is processed. The FOi function converts data by the FI function and the exclusive OR, using round keys KOi1 through KOi4 and round keys KIi1 through KIi3.
As illustrated in FIG. 4, the FI function is a function in a MISTY structure which inputs 16-bit data, converts it to 16-bit data and outputs it. The 16-bit data inputted to the FI function is divided into left nine bits and right seven bits and is converted by a non-linear function (non-linear conversion) S7 and S9, zero-extend and truncate. The zero-extend converts 7-bit data to 9-bit data by adding two higher-order bits (“00”) to 7-bit data. The truncate converts 9-bit data to 7-bit data by deleting two higher-order bits from 9-bit data. The FIij function converts data using keys KIij1 and KIij2. The KIij 1 and KIij2 are the 7-bit left data and the 9-bit right data, respectively, of the round key KIij.
Next, the MISTY structure will be explained. The MISTY structure constitutes the respective stages of the FO and FI functions. As illustrated in FIG. 3, the MISTY structure of the FO function arranges a first exclusive OR for inputting a round key KOij (j=1 to 3) to a left system data path, an FI function for inputting a round key KIij (j=1 to 3) below it and a second exclusive OR below the FI function, and calculates the exclusive OR of the output of the FI function and data branched and inputted from a right system data path by the second exclusive OR. Then, the calculation result of the second exclusive OR is inputted to the right system data path in a subsequent stage. Data flowing through the right system data path in the previous stage is inputted to the left system data path in a subsequent stage. As illustrated in FIG. 4, in the case of an FI function, in the above-described MISTY structure of the FO function, the FI function is replaced with a non-linear function S9 or S7 and one or two exclusive Ors are arranged below the non-linear function. The exclusive OR arranged immediately below the non-linear function S9 or S7 corresponds to the second exclusive OR in the MISTY structure of the FO function. Although the configuration of the MISTY structure is explained using the MISTY structures of an FO function and an FI function as examples above, other data conversion functions than these have various types of MISTY structures.
As illustrated in FIGS. 5A and 5B, the FL function and the FL−1 function input 32-bit data, convert it to 32-bit data and output it. The 32-bit input data is divided into two of 16 bits and is processed. The FL function is converted by an AND and an OR. KLi1 and KLi2 are the first and second 16-bit data, respectively, from the left of a round key KLi. The FL−1 function has an arrangement obtained by vertically inverting the respective components of the FL function. The FL−1 function decrypts the 32-bit data encrypted by the FL function.
{Configuration of Extended Generation Key Process Unit}
Next, the configuration of the extended key generation unit 10 for generating a round key used for the above FO function, FI function, FL function and FL−1 function will be explained.
The extended key generation unit 10 generates a 128-bit extended key K′ from a 128-bit private key K. In this case, the private key K is divided in units of 16 bits and it is defined that the i-th 16-bit data from the left is Ki (i=1 to 8). The extended key K′ is divided in units of 16 bits and it is defined that the i-th 16-bit data from the left is K′i (i=1 to 8). It is assumed that K9=K1. It is defined that when i exceeds eight, Ki and K′i mean Ki-8 and K′i-8, respectively.
The extended key generation unit 10 generates an extended key K′ from a private key K, using the FI function. The configuration of the extended key generation unit 10 is disclosed in FIG. 5 of the above non-patent document 1. The relations between the round keys KOij, KIij and KLij and actual keys (private key K and extended key K′) are as illustrated in the following Table 1.
KOi1KOi2KOi3KOi4Kii1Kii2Kii3KLi1KLi2KeyKiKi+2Ki+7Ki+4K′i+5K′i+1K′i+3K(i+1)/2K′(i+1)/2+6(when i is odd)(when i is odd)K′i/2+2K′i/2+4(when i is even)(when i is even)
As described above, the MISTY 1 includes an FO function, an FL function, an FL−1 function and an exclusive OR. As described above, the FO function includes an FI function and an exclusive OR. The extended key generation unit 10 generates an extended key K′ using the FI function. Therefore, the process time of the FI function occupies a large weight in the entire process time (time required for encryption and decryption processes) of the MISTY 1. Therefore, in the high-speed implementation of hardware in the MISTY 1, the performance of the FI function becomes an important factor for determining the performance of the MISTY 1. Therefore, in the high-speed implementation of hardware in the MISTY 1, it is required that the FI function is optimized.
{Configuration of Conventional FI Function}
FIG. 6 illustrates how to implement a conventional FI function. FIG. 6 is obtained by modifying the description of an FI function, disclosed in the specification of the MISTY 1 illustrated in FIG. 4 to a logically equivalent description.
As illustrated in FIG. 6, in the FI function, inputted 16-bit data is divided into left nine bits and right seven bits. The above 9-bit data and 7-bit data are processed on the left (left system) paths 100 and right (right system) paths 110, respectively. In FIG. 6, a route (data path) becoming a critical path in the FI function is indicated by a thick line 100. In this case, the critical path means a route (data path) in which its process time becomes a maximum in the FI function.
A critical path 100 includes two non-linear functions (non-linear conversion) S9 and three exclusive Ors and process all pieces of data in nine bits. The non-linear function S9 is a 9-bit input/output non-linear function and its hardware implementation is made by a non-linear conversion table or the like. This non-linear conversion table is implemented, for example, in semiconductor memory, such as ROM (read-only memory) or the like. Thus, since the process of the non-linear function S9 accompanies a memory access, its process time increases compared with the process of an exclusive OR.
FIG. 7 is a configuration including FI functions (FIi1 to FIi3) and an exclusive OR 60 positioned immediately below it, in each round of the FO function illustrated in FIG. 3.
Exclusive ORs 60a and 60b illustrated in FIG. 7 are obtained by dividing the 16-bit exclusive OR 60 illustrated in FIG. 3 into a 9-bit exclusive OR and a 7-bit exclusive OR, respectively. The exclusive ORs 60a and 60b are the 9-bit and 7-bit exclusive ORs, respectively. A critical path 200 illustrated in FIG. 7 includes two non-linear functions S9 and four exclusive Ors and processes all pieces of data in nine bits. The right system path 210 includes one non-linear function S7 and three exclusive ORs and processes all pieces of data in seven bits.
In order to process the FI and FO functions in high speed, it is good idea that the critical paths 100 and 200 illustrated in FIGS. 6 and 7 is shortened. In this case, “the shortening of a critical path” means the deletion of the components of the critical path. However, in the FI function of the MISTY 1, a 16-bit input is divided into the different number of bits of 9 bits and 7 bits, which are processed two of left and right paths (data paths), respectively. Thus, since FI function has a non-uniform structure in which the respective numbers of bits of data paths differ between the left and right systems, it is not easy to perform a logical conversion while maintain its equivalence. Therefore, difficulty in logical conversion becomes an obstacle in the high-speed process of the FI function in the MISTY 1.    Patent document 1: Japanese Laid-open Patent Publication No. 2004-240427    Patent document 2: Japanese Patent No. 3088337    Non-patent document 1: Encryption technology specification MISTY 1    Non-patent document 2: Mitsuru Matsui, “Block Encryption Algorithm MISTY 1”, Technical Report of IEICE, ISEC96-11 (July 1996)